package gold.digger;

import gold.vo.ListNode;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC148 {

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * @return:
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;//递归终止条件
        ListNode slow = head, fast = head, pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;//这一步很关键，防止出现环
        return merge(sortList(head), sortList(slow));
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        LC148 an = new LC148();
        System.out.println(an.sortList(null));
    }
}
